//给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。 
//
// 异位词 指字母相同，但排列不同的字符串。 
//
// 
//
// 示例 1: 
//
// 
//输入: s = "cbaebabacd", p = "abc"
//输出: [0,6]
//解释:
//起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
//起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
// 
//
// 示例 2: 
//
// 
//输入: s = "abab", p = "ab"
//输出: [0,1,2]
//解释:
//起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
//起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
//起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
// 
//
// 
//
// 提示: 
//
// 
// 1 <= s.length, p.length <= 3 * 104 
// s 和 p 仅包含小写字母 
// 
// Related Topics 哈希表 字符串 滑动窗口 
// 👍 626 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
func findAnagrams(s string, p string) []int {

    // 滑动窗口

    need, window := make(map[byte]int), make(map[byte]int)

    for i := range p {
        need[p[i]]++
    }

    left, right := 0, 0

    matchNum := 0

    result := []int{}

    for right < len(s) {
        v1 := s[right]
        right++

        if _, ok := need[v1]; ok {  // 出现不需要的字段 直接放弃 重置window
            window[v1]++

            if window[v1] == need[v1] {
                matchNum++
            }
        }

        // 这里有长度卡着 不用考虑 某个字符 超限的情况， 超限会导致其他字符不够
        // 而match每次加减 都是在当前处于==情况下处理  加多了再减不会更改到matchNum

        for right - left >= len(p) { // 长度相等 或大于
            if matchNum == len(need) {
                result = append(result, left)
            }

            v2 := s[left]
            left++

            if _, ok := need[v2]; ok {
                if window[v2] == need[v2] {
                    matchNum--
                }
                window[v2]--
            }
        }
    }

    return result
}
//leetcode submit region end(Prohibit modification and deletion)
